package problems.daily;

import java.util.HashMap;

/**
 * 904. 水果成篮
 * <p>https://leetcode.cn/problems/fruit-into-baskets/</p>
 * <p>滑动窗口</p>
 *
 * @author habitplus
 * @since 2022/10/17 16:32
 */
public class DT904 {
    /**
     * hash map 实现
     */
    public int totalFruit3(int[] fruits) {

        if (fruits == null || fruits.length < 1) return 0;

        HashMap<Integer, Integer> cntMap = new HashMap<>();
        int n = fruits.length;
        int l = 0;
        int ret = 0;
        int cnt;

        for (int r = 0; r < n; ++r) {
            cntMap.put(fruits[r], cntMap.getOrDefault(fruits[r], 0) + 1);

            // 超过了两种水果，
            while (cntMap.size() > 2) {
                cnt = cntMap.get(fruits[l]);
                if (cnt > 1) {
                    cntMap.put(fruits[l], cnt - 1);
                } else {
                    cntMap.remove(fruits[l]);
                }
                ++l;
            }

            ret = Math.max(r - l + 1, ret);
        }

        return ret;
    }

    /**
     * 变量实现
     */
    public int totalFruit2(int[] fruits) {
        if (fruits == null || fruits.length < 1) return 0;
        int n = fruits.length;
        int first = -1, firstCnt = 0;
        int second = -1, secondCnt = 0;
        int total = 0;
        int ret = 0;
        int l = 0;

        for (int r = 0; r < n; r++) {
            if (first < 0) {
                first = r;
                firstCnt = 1;
                ++total;
            } else if (fruits[first] == fruits[r]) {
                ++firstCnt;
            } else if (second < 0) {
                second = r;
                secondCnt = 1;
                ++total;
            } else if (fruits[second] == fruits[r]) {
                ++secondCnt;
            } else {
                ++total;
            }

            while (total > 2) {
                if (fruits[l] == fruits[first]) {
                    --firstCnt;
                    if (firstCnt < 1) {
                        first = r;
                        firstCnt = 1;
                        --total;
                    }
                } else {
                    --secondCnt;
                    if (secondCnt < 1) {
                        second = r;
                        secondCnt = 1;
                        --total;
                    }
                }
                ++l;
            }
            ret = Math.max(r - l + 1, ret);
        }

        return ret;
    }

    /**
     * 变量实现（优化）
     */
    public int totalFruit1(int[] fruits) {
        if (fruits == null || fruits.length < 1) return 0;

        // 区间左端点
        int l = 0;

        // [l, r) 区间内，第一种水果的最后一个下标
        int first = -1;
        // [l, r) 区间内，第二种水果的最后一个下标
        int second = -1;
        // [l, r] 中的水果种类数
        int total = 0;

        int ret = 0;


        for (int r = 0; r < fruits.length; ++r) {
            if (first < 0 || fruits[first] == fruits[r]) {
                total += first < 0 ? 1 : 0;
                first = r;
            } else if (second < 0 || fruits[second] == fruits[r]) {
                total += second < 0 ? 1 : 0;
                second = r;
            } else {
                ++total;
            }

            // 当前 fruits[r] 为第三种水果
            if (total > 2) {
                --total;
                if (first > second) {
                    l = second + 1;
                    second = r;
                } else {
                    l = first + 1;
                    first = r;
                }
            }
            ret = Math.max(r - l + 1, ret);
        }

        return ret;
    }

    public int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length < 1) return 0;

        // 区间左端点
        int l = 0;

        // [l, r) 区间内，第一种水果的最后一个下标
        int first = -1;
        // [l, r) 区间内，第二种水果的最后一个下标
        int second = -1;

        int ret = 0;

        for (int r = 0; r < fruits.length; ++r) {
            if (first < 0 || fruits[first] == fruits[r]) {
                first = r;
            } else if (second < 0 || fruits[second] == fruits[r]) {
                second = r;
            } else {
                // 当前 fruits[r] 为第三种水果
                // 去掉离当前位置最远的那一种水果
                // 同时更新左边界
                if (first > second) {
                    l = second + 1;
                    second = r;
                } else {
                    l = first + 1;
                    first = r;
                }
            }
            // 计算最大长度
            ret = Math.max(r - l + 1, ret);
        }

        return ret;
    }

}
